package org.liaohailong.helloworld.practice;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Author: liaohailong
 * Time: 2021/6/10 17:51
 * Describe: 初级算法 - 树练习
 */
public class TreePractice {
    public static final class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static TreeNode create(Integer[] arr) {
        if (arr.length < 1 || arr[0] == null) return null;
        LinkedList<TreeNode> bfs = new LinkedList<>();
        TreeNode root = new TreeNode(arr[0]);
        bfs.add(root);
        int pos = 0;
        while (!bfs.isEmpty()) {
            pos++;
            TreeNode parent = bfs.pollFirst();
            if (pos < arr.length) {
                Integer val = arr[pos];
                if (val != null) {
                    parent.left = new TreeNode(val);
                    bfs.add(parent.left);
                }
            } else break;
            pos++;
            if (pos < arr.length) {
                Integer val = arr[pos];
                if (val != null) {
                    parent.right = new TreeNode(val);
                    bfs.add(parent.right);
                }
            } else break;
        }

        return root;
    }

    // LC 二叉树的最大深度
//    public int maxDepth(TreeNode root) {
//        if (root == null) return 0;
//        int depth = 0;
//        LinkedList<TreeNode> bfs = new LinkedList<>();
//        bfs.add(root);
//
//        while (!bfs.isEmpty()) {
//            int size = bfs.size();
//            while (size-- > 0) {
//                TreeNode treeNode = bfs.pollFirst();
//                if (treeNode.left != null) bfs.addLast(treeNode.left);
//                if (treeNode.right != null) bfs.addLast(treeNode.right);
//            }
//            depth++;
//        }
//
//        return depth;
//    }

    // LC 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    // LC 验证二叉搜索树
    public boolean isValidBST(TreeNode root) {
        return _isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean _isValidBST(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return _isValidBST(node.left, min, node.val) && _isValidBST(node.right, node.val, max);
    }

    // LC 对称二叉树
    public boolean isSymmetric(TreeNode root) {
        return _isSymmetric(root.left, root.right);
    }

    public boolean _isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return _isSymmetric(left.left, right.right) && _isSymmetric(left.right, right.left);
    }

    // LC 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        _levelOrder(root, 0, result);
        return result;
    }

    private void _levelOrder(TreeNode root, int depth, List<List<Integer>> res) {
        if (root == null) return;
        List<Integer> integers;
        if (depth < res.size()) {
            integers = res.get(depth);
        } else {
            integers = new LinkedList<>();
            res.add(integers);
        }
        integers.add(root.val);

        depth++;
        _levelOrder(root.left, depth, res);
        _levelOrder(root.right, depth, res);
    }

    // LC 将有序数组转换为二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    public TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) return null;
        int mid = (end + start) >> 1;
        TreeNode parent = new TreeNode(nums[mid]);
        parent.left = sortedArrayToBST(nums, start, mid - 1);
        parent.right = sortedArrayToBST(nums, mid + 1, end);
        return parent;
    }

    int[] pre;
    Map<Integer, Integer> inorderMap = new HashMap<>();

    // LC 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 画图判断，is ie ri ps pe

        pre = preorder;
        // 构建一个map，方便寻找中序遍历中root节点的下标位置
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }

        return _buildTree(0, inorder.length - 1, 0, preorder.length - 1);
    }

    private TreeNode _buildTree(int is, int ie, int ps, int pe) {
        if (is > ie || ps > pe) return null;

        int rootVal = pre[ps];
        TreeNode root = new TreeNode(rootVal);

        Integer ri = inorderMap.get(rootVal);
        if (ri == null) return null;

        int lc = ri - is; // left count

        root.left = _buildTree(is, ri - 1, ps + 1, ps + lc);
        root.right = _buildTree(ri + 1, ie, ps + lc + 1, pe);

        return root;
    }

}
